package dp;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class leetCode42_trap {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trap = trap(nums);
        System.out.println(trap);

    }

    public static int trap(int[] height) {
        if (height == null || height.length < 2) return 0;
        int sum = 0;
        int max = 0;
        for (int i : height) {
            max = Math.max(max, i);
            sum += i;
        }
        int full = max * height.length;
        int suml = 0;
        int maxl = 0;
        for (int i = 0; i < height.length; i++) {
            maxl = Math.max(maxl,height[i]);
            suml += maxl;
        }

        int sumr = 0;
        int maxr = 0;
        for (int i = height.length - 1; i >=  0; i--) {
            maxr = Math.max(maxr,height[i]);
            sumr += maxr;
        }

        return sumr + suml - full - sum;

    }

    public static int trap2(int[] height) {
        if(height == null || height.length == 0) return 0;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            sum+=height[i];
            max = Math.max(height[i],max);
        }
        int full = max * height.length;

        int leftSum = 0;
        int leftMax = 0;
        for (int i = 0; i < height.length; i++) {
            leftMax = Math.max(height[i],leftMax);
            leftSum = leftSum + leftMax;
        }

        int rightSum = 0;
        int rightMax = 0;

        for (int i = height.length - 1; i >= 0; i--) {
            rightMax = Math.max(height[i],rightMax);
            rightSum = rightSum + rightMax;
        }

        return leftSum + rightSum - full - sum;

    }

}
